#include <stdlib.h>
#include "link_1.h"

//链表初始化函数
void link_init(link *p_link) {
	p_link->head.p_next = &p_link->tail;	//把头节点和尾节点连接起来形成一个空的线性链式物理结构
	p_link->tail.p_prev = &p_link->head;	//尾节点向前指向头节点
	p_link->tail.p_next = NULL;		//把尾节点里指向后一个节点的指针设置为空指针
	p_link->head.p_prev = NULL;		//把头节点里指向前一个节点的指针设置为空指针
	p_link->p_cur = NULL;			//《遍历指针成员变量为空表示非遍历状态》
}

//链表清理函数
void link_deinit(link *p_link) {
	node *p_first = NULL,  *p_mid = NULL,  *p_last = NULL;
	p_link->p_cur = NULL;		//《清理函数也需要设置为非遍历状态》
	//每次循环把最前面的有效节点删除并释放
	while(p_link->head.p_next != &p_link->tail) {	//从头节点后面不是尾节点就说明存在有效节点，循环就应该继续
		//让三个节点指针指向链表最前面的三个节点
		p_first = &p_link->head;
		p_mid = p_first->p_next;
		p_last = p_mid->p_next;
		//把p_mid指针指向的节点从链式物理结构里摘除
		p_first->p_next = p_last;
		p_last->p_prev = p_first;
		//释放p_mid指针指向的节点
		free(p_mid);
		p_mid = NULL;
	}
}

//获得数字个数的函数
int link_size(const link *p_link) {
	const node *p_tmp = NULL;
	int cnt = 0;
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		const node *p_first = p_tmp;
		const node *p_mid = p_first->p_next;
		const node *p_last = p_mid->p_next;
		if(p_mid != &p_link->tail) {	//当p_mid指针不是指向尾节点就一定指向一个有效节点
			cnt++;	//数一个数字
		}
	}
	return cnt;
}

//判断链表是否空的函数
int link_empty(const link *p_link) {
	return p_link->head.p_next == &p_link->tail;	//头结点后面是不是尾节点
}

//在链表最前面插入数字的函数
int link_add_head(link *p_link, int val) {
	node *p_node = NULL;
	p_link->p_cur = NULL;	//《结束遍历过程》
	p_node = (node*)malloc(sizeof(node));	//动态分配一个节点用来记录新数字
	node *p_first =NULL,  *p_mid = NULL,  *p_last = NULL;
	if(!p_node) {
	//动态内存分配失败
		return 0;
	}
	p_node->val = val;	//把新数字记录到动态分配节点里
	p_node->p_next = NULL;
	p_node->p_prev = NULL;	//把动态分配节点向前的指针也设置为空指针
	//把三个节点指针指向链表最前面的三个节点
	p_first = &p_link->head;
	p_mid = p_first->p_next;
	p_last = p_mid->p_next;
	//把新节点插入到p_first和p_mid中间
	p_first->p_next = p_node;
	p_node->p_next = p_mid;
	//也需要反向操作
	p_mid->p_prev = p_node;
	p_node->p_prev = p_first;
	return 1;
}

//在链表末尾插入新数字的函数
int link_append(link *p_link, int val) {
	node *p_node = NULL;
	p_link->p_cur = NULL;	//《结束遍历过程》
	p_node = (node*)malloc(sizeof(node));	//动态分配节点用来存放新数字
	node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
	if(!p_node) {
	//动态分配失败
		return 0;
	}
	p_node->val = val;	//把新数字记录到新节点里
	p_node->p_next = NULL;
	p_node->p_prev = NULL;
	p_first = p_link->tail.p_prev;	//p_first指针指向尾节点前面的节点
	p_mid = p_first->p_next;	//p_mid指针指向尾节点
	p_last = p_mid->p_next;
	//把新节点插入到p_mid和p_last中间
	p_first->p_next = p_node;
	p_node->p_next = p_mid;
	p_mid->p_prev = p_node;
	p_node->p_prev = p_first;
	return 1;
}
/*int link_append(link *p_link, int val) {
	node *p_node = NULL;
	p_link->p_cur = NULL;	//《结束遍历过程》
	p_node = (node*)malloc(sizeof(node));	//动态分配节点用来记录新数字
	node *p_tmp = NULL;
	if(!p_node) {
	//动态分配失败
		return 0;
	}
	p_node->val = val;	//把新数字记录到动态分配节点里
	p_node->p_next = NULL;
	p_node->p_prev = NULL;	//反向操作
	//编写for循环找到链表末尾的位置
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		node *p_first = p_tmp;
		node *p_mid = p_first->p_next;
		node *p_last = p_mid->p_next;
		if(p_mid == &p_link->tail) {	//p_mid指针指向尾节点，p_first指针和p_mid指针中间的位置就是要插入的位置
			p_first->p_next = p_node;
			p_node->p_next = p_mid;
			//反向操作
			p_mid->p_prev = p_node;
			p_node->p_prev = p_first;
			break;
		}
	}
	return 1;
}*/

//按照从小到大的顺序在链表中间插入新数字的函数
int link_insert(link *p_link, int val) {
	node *p_node = NULL;
	p_link->p_cur = NULL;	//《结束遍历过程》
	p_node = (node*)malloc(sizeof(node));	//动态分配节点用来记录数字
	node *p_tmp = NULL;
	if(!p_node) {
	//动态分配失败
		return 0;
	}
	p_node->val = val;	//把新数字记录到动态分配节点里
	p_node->p_next = NULL;
	p_node->p_prev = NULL;	//反向操作
	//编写for循环查找要插入的位置
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		node *p_first = p_tmp;
		node *p_mid = p_first->p_next;
		node *p_last = p_mid->p_next;
		if(p_mid == &p_link->tail /*p_mid指针指向尾节点*/ || p_mid->val > val /*p_mid指针指向节点里的数字比要插入的数字大*/) {
			//把新节点插入到p_first指针和p_mid指针之间
			p_first->p_next = p_node;
			p_node->p_next = p_mid;
			//反向操作
			p_mid->p_prev = p_node;
			p_node->p_prev = p_first;
			break;
		}
	}
	return 1;
}

//删除最前面数字的函数
int link_remove_head(link *p_link) {
	p_link->p_cur = NULL;	//《结束遍历过程》
	node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
	if(p_link->head.p_next == &p_link->tail) {
	//如果头节点后面就是尾节点就无法删除任何节点
		return 0;
	}
	p_first = &p_link->head;
	p_mid = p_first->p_next;
	p_last = p_mid->p_next;
	//把p_mid指向的节点从链式物理结构中摘出来
	p_first->p_next = p_last;
	p_last->p_prev = p_first; //反向操作
	//释放p_mid指针指向的节点
	free(p_mid);
	p_mid = NULL;
	return 1;
}

//删除最后一个有效数字的函数
int link_remove_tail(link *p_link) {
	p_link->p_cur = NULL;	//《结束遍历过程》
	node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
	if(p_link->head.p_next == &p_link->tail) {
	//链表是空的
	return 0;
	}
	p_last = &p_link->tail;	//p_last指针指向尾节点
	p_mid = p_last-> p_prev;	//p_mid指针指向最后一个有效节点
	p_first = p_mid->p_prev;
	//把p_mid指针指向的节点从链式物理结构里摘出来
	p_first->p_next = p_last;
	p_last->p_prev = p_first;
	//释放p_mid指针指向的节点
	free(p_mid);
	p_mid = NULL;
	return 1;
}
/*int link_remove_tail(link *p_link) {
 	p_link->p_cur = NULL;	//《结束遍历过程》
	node *p_tmp = NULL;
	//使用for循环找到最后一个有效数字所在的节点
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		node *p_first = p_tmp;
		node *p_mid = p_first->p_next;
		node *p_last = p_mid->p_next;
		if(p_last == &p_link->tail) {	//当p_last指针指向尾节点的时候p_mid指针指向最后一个有效节点
			//把p_mid指针指向的节点从链式物理结构里摘出来
			p_first->p_next = p_last;
			p_last->p_prev = p_first; //反向操作
			//释放p_mid指针指向的节点
			free(p_mid);
			p_mid = NULL;
			return 1;
		}
	}
	return 0;
}*/

//删除链表中间某个数字的函数
int link_remove(link *p_link, int val) {
	p_link->p_cur = NULL;	//《结束遍历过程》
	node *p_tmp = NULL;
	//编写for循环找到要删除的数字所在的节点
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		node *p_first = p_tmp;
		node *p_mid = p_first->p_next;
		node *p_last = p_mid->p_next;
		if(p_mid != &p_link->tail/*p_mid指针没有指向尾节点*/ && p_mid->val == val/*p_mid指针指向的节点就是要删除的节点*/) {
			//把p_mid指针指向的节点从链式物理结构里摘出来
			p_first->p_next = p_last;
			p_last->p_prev = p_first; //反向操作
			//释放p_mid指针指向的节点
			free(p_mid);
			p_mid = NULL;
			return 1;
		}
	}
	return 0;
}

//获得最前面数字的函数
int link_get_head(const link *p_link, int *p_val) {
	const node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
	if(p_link->head.p_next == &p_link->tail) {
	//从头结点向后指向尾节点无法获得数字
		return 0;
	}
	//让三个节点指针指向链表里最前面的三个节点
	p_first = &p_link->head;
	p_mid = p_first->p_next;
	p_last = p_mid->p_next;
	
	*p_val = p_mid->val;	//把p_mid指针指向节点里面的数字传递给调用函数
	return 1;
}

//获得链表里最后一个数字的函数
int link_get_tail(const link *p_link, int *p_val) {
	const node *p_first = NULL, *p_mid = NULL, *p_last = NULL;
	if(p_link->head.p_next == &p_link->tail) {
	//链表是空的
		return 0;
	}
	//让三个节点指针指向链表最后的三个节点
	p_last = &p_link->tail;
	p_mid = p_last->p_prev;
	p_first = p_mid->p_prev;
	*p_val = p_mid->val;	//把p_mid指针指向的节点里的数字传递给调用函数
	return 1;
}
/*int link_get_tail(const link *p_link, int *p_val) {
	const node *p_tmp = NULL;
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		const node *p_first = p_tmp;
		const node *p_mid = p_first->p_next;
		const node *p_last = p_mid->p_next;
		if(p_last == &p_link->tail) {	//p_last指针指向尾节点就表示p_mid指针指向了最后一个有效节点
			*p_val = p_mid->val;	//把p_mid指针指向的节点里的数字传递给调用函数
			return 1;
		}
	}
	return 0;
}*/

//根据编号获得数字的函数
int link_get(const link *p_link, int *p_val, int sn) {
	const node *p_tmp = NULL;
	int cnt = 0;
	//编写循环找到指定的节点
	for(p_tmp = &p_link->head; p_tmp != &p_link->tail; p_tmp = p_tmp->p_next) {
		const node *p_first = p_tmp;
		const node *p_mid = p_first->p_next;
		const node *p_last = p_mid->p_next;
		if(p_mid != &p_link->tail /*p_mid指针不是指向尾节点*/&& cnt == sn) {
		//p_mid指针指向的节点就是要找的节点
			*p_val = p_mid->val;	//把p_mid指针指向节点里的数字传递给调用函数
			return 1;
		}
		cnt++;
	}
	return 0;
}

//《开始从前向后遍历链表的函数》
void link_begin(link *p_link) {
	p_link->p_cur = &p_link->head;	//把头节点设置为上一个操作的节点
}

//《在从前向后的遍历过程中获得下一个数字的函数》
int link_next(link *p_link, int *p_val) {
	if(!p_link->p_cur) {
	//链表没有处于遍历过程中
		return 0;
	}
	p_link->p_cur = p_link->p_cur->p_next;	//找到这次要操作的节点并记录下来
	if(p_link->p_cur == &p_link->tail) {
	//这次要操作的节点是尾节点就表示遍历过程已经结束了
		p_link->p_cur = NULL;	//结束遍历过程
		return 0;
	}
	else {
		*p_val = p_link->p_cur->val;	//把这次要要操作的节点内容传递给调用函数
		return 1;
	}
}

//《开始从后向前遍历过程的函数》
void link_rbegin(link *p_link) {
	p_link->p_cur = &p_link->tail;	//把尾节点设置为上一次操作的节点
}

//《在从后向前遍历过程中获得前一个数字的函数》
int link_prev(link *p_link, int *p_val) {
	if(!p_link->p_cur) {
	//没有处于遍历状态
		return 0;
	}
	p_link->p_cur = p_link->p_cur->p_prev;	//找到这次要操作的节点并记录下来
	if(p_link->p_cur == &p_link->head){
	//这次要操作的节点是头节点就表示遍历过程已经结束了
		p_link->p_cur = NULL;	//结束遍历过程
		return 0;
	}
	else {
		*p_val = p_link->p_cur->val;	//把这次要操作的节点内容传递给调用函数
		return 1;
	}
}
